package com.gzl.exercise;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 缺失的第一个正数
 * @DESCRIPTION: 困难
 * @USER: gaozengliang
 * @DATE: 2023/9/13
 */
public class 缺失的第一个正数 {
    /**
     * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
     *
     * 示例 1：
     * 输入：nums = [1,2,0]
     * 输出：3
     *
     * 示例 2：
     * 输入：nums = [3,4,-1,1]
     * 输出：2
     *
     * 示例 3：
     * 输入：nums = [7,8,9,11,12]
     * 输出：1
     *
     * 提示：
     * 1 <= nums.length <= 5 * 10^5
     * -2^31 <= nums[i] <= 2^31 - 1
     * */

    // 不是最优，但能通过
    @Test
    void test(){
        int[] nums = {7,8,9,11,12};
//        int[] nums = {3,4,-1,1};
//        int[] nums = {1,2,0};
//        int[] nums = {-Integer.MAX_VALUE};
//        int[] nums = {1,1};

        int min = 1;    //最小正数
        int temp = 1;   //当前最小正数
        //排序
        Arrays.sort(nums);

        for (int n=0;n<nums.length;n++){
            if (nums[n]>0) {
                int i = temp;
                while (true) {
                    if (i < nums[n]) {
                        min = i;
                        break;
                    }else if (i == nums[n]){
                        temp = nums[n]+1;
                    }
                    //如果已遍历至最后，最小正数就是当前得到的最小正数
                    if (n == nums.length-1){
                        min = temp;
                    }
                    // 遍历至最后，当前最小正数依然大于数组最大值，i为最小正数 1，说明该数组中值全为负数，结束
                    if (i >= nums[n]){
                        break;
                    }
                    i++;
                }
            }
        }
        System.out.println(min);
    }

    //官方题解，详细查看下面链接
    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * 方法一：模拟哈希表
     * 仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。因此，我们可以考虑将给定的数组设计成哈希表的「替代产品」。
     *
     * 实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：
     *
     * 我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
     *
     * 那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：
     *  我们将数组中所有小于等于 0 的数修改为 N+1；
     *  我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣ ∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
     *  在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。
     *
     *
     * 方法二：置换
     * 除了打标记以外，我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：
     * 如果数组中包含 x∈[1,N]，那么恢复后，数组的第 x−1 个元素为 x。
     *
     * 在恢复后，数组应当有 [1, 2, ..., N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2。
     *
     * 那么我们如何将数组进行恢复呢？我们可以对数组进行一次遍历，对于遍历到的数 x=nums[i]，如果 x∈[1,N]，我们就知道 x 应当出现在数组中的 x−1 的位置，因此交换 nums[i] 和 nums[x−1]，这样 x 就出现在了正确的位置。在完成交换后，新的 nums[i] 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到 x∉[1,N]。
     *
     * 注意到上面的方法可能会陷入死循环。如果 nums[i] 恰好与 nums[x−1] 相等，那么就会无限交换下去。此时我们有 nums[i]=x=nums[x−1]，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。
     *
     * 由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 N，整个方法的时间复杂度为 O(N)。
     *
     * */

    //方法一：模拟哈希表
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }

    //方法二：置换
    public int firstMissingPositive2(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}
